最後一篇想不到要寫什麼跟vSAN相關的主題，不如就來寫一個和Cache相關的主題吧！畢竟他和vSAN一樣都是計算機儲存的範疇

什麼是 Cache？

在我們的電腦系統中，Cache（快取）扮演著至關重要的角色。快取是一種高效能的臨時儲存區域，用於儲存經常被訪問的資料，以加速資料讀取和寫入的速度。想像一下冰箱裡的食物，快取就像是你放在冰箱門邊的零食，方便隨時取用，而不是藏在冰箱深處的冷凍食品。

一個好的 Cache 應該具備哪些特性？

1. 高命中率: 快取的主要目的是提高資料訪問速度，所以高命中率是衡量一個好快取的關鍵指標。這就像你想從冰箱裡拿出一瓶飲料，理想情況下，它應該總是放在你容易找到的位置。
2. 低延遲: 快取應該能夠快速響應資料請求，減少讀寫延遲。這就像你想要吃東西時，食物應該馬上能夠取到，而不是還需要解凍和加熱。
3. 高效資源利用: 快取應該能夠高效地利用有限的儲存資源，儘可能儲存更多的有用資料。這就像冰箱空間有限，你應該放進去的是經常吃的食物，而不是占空間卻不常吃的。

當然，快取的速度很快，相對應的缺點就是「貴」！

傳統的 LRU 策略

在快取策略中，LRU（Least Recently Used）是一種經典的演算法。LRU 的基本策略是當快取空間不足時，淘汰最久未被使用的資料。這就像在冰箱裡，定期清理那些已經很久沒吃過的食物，確保新的食物有地方放。

LRU 的資料結構

要實現 LRU，我們需要兩個主要的資料結構：

1. 哈希表（HashMap）: 用來快速查找資料的位置。
2. 雙向鏈表（Doubly Linked List）: 用來記錄資料的使用順序。
   雙向鏈表可以讓我們在常數時間內（O(1)）移動和刪除節點，哈希表則可以讓我們在常數時間內（O(1)）找到需要的節點。 下面一個簡單的 Python 範例，展示了 LRU 演算法：

# 定義 Doubly Linked List
class Node:
    def __init__(self, key, value):
        self.key = key     # 一個整數key，佔用 4 bytes
        self.value = value # 通常是一個pointer，佔用 8 bytes
        self.prev = None   # 前驅指標，佔用 8 bytes
        self.next = None   # 後繼指標，佔用 8 bytes

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # key:   int value
        # value: Node address
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            node_to_remove = self.head.next
            self._remove(node_to_remove)
            del self.cache[node_to_remove.key]

    def _remove(self, node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

    def _add(self, node):
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

記憶體用量

LRU 的記憶體用量主要來自兩部分：

1. 資料儲存: 儲存實際的資料。
2. 資料結構: 用來追蹤資料使用情況的雙向鏈表（一個節點28 bytes至少）和哈希表。

每個節點在雙向鏈表中需要儲存前驅（prev）和後繼（next）指標，這增加了記憶體消耗。隨著資料規模增大，這些額外的儲存開銷在系統變大所需快取增加後會變得非常顯著。

為何 LRU 在大記憶體下會使用更多的記憶體？

當快取規模增大時，雙向鏈表和哈希表的節點數量也會隨之增加。這意味著需要更多的記憶體來儲存這些額外的指標和哈希表條目。特別是在高併發環境下，管理這些資料結構會導致更多的記憶體碎片和開銷。隨著摩爾定律，現在的系統越來越大、資源越來越多，可用的Cache空間也是越來越大，那有沒有什麼演算法能同時達到LRU的cache命中率，並且隨著Cache增大還能減少記憶體的佔用呢？

S3-FIFO

S3-FIFO（simple, scalable, space-efficient first in first out）是一種新穎的快取管理策略，旨在解決 LRU 記憶體用量大的缺點。S3-FIFO 使用三個隊列（Queue）：S快取、M快取、和G快取來管理資料。這些隊列的具體運作如下：
1. S快取：這個隊列用來儲存新插入的資料。當資料被訪問時，訪問計數會增加。如果S快取滿了，就會根據訪問計數決定是將資料移動到M快取還是G快取。
2. M快取：這個隊列用來儲存經常被訪問的資料。當M快取滿了時，最舊的資料會被移出。這些資料會根據訪問計數決定是否重新插入M快取或移至G快取。
3. G快取：這個隊列用來儲存那些在S快取和M快取中被淘汰的資料鍵值（不儲存實際資料和訪問計數）。它用來記錄哪些資料最近被淘汰，以防止頻繁的重複插入(重複的記憶體分配和釋放)。

運作例子

假設我們有一個 S3-FIFO 快取系統，S 容量為 3，M 容量為 5，G 容量為 2。以下是一個運作過程的例子：

1. 插入資料 1, 2, 3 到小快取 S：
   • S: [1, 2, 3]
   • M: []
   • G: []
2. 插入資料 4 到 S（S 滿了，1 被移除）：
   • 1 沒有被訪問過，移至 G
   • S: [2, 3, 4]
   • M: []
   • G: [1]
3. 插入資料 5 到 S（S 滿了，2 被移除）：
   • 2 沒有被訪問過，移至 G
   • S: [3, 4, 5]
   • M: []
   • G: [1, 2]
4. 插入資料 6 到 S（S 滿了，3 被移除）：
   • 3 沒有被訪問過，G 滿了，移除 G 最舊的 1
   • S: [4, 5, 6]
   • M: []
   • G: [2, 3]
5. 訪問資料 4（增加 4 的訪問計數）：
   • S: [4(1), 5, 6]
   • M: []
   • G: [2, 3]
6. 插入資料 7 到 S（S 滿了，4 被移除）：
   • 4 被訪問過，移至 M
   • S: [5, 6, 7]
   • M: [4(1)]
   • G: [2, 3]
7. 插入資料 8 到 S（S 滿了，5 被移除）：
   • 5 沒有被訪問過，移至 G
   • S: [6, 7, 8]
   • M: [4(1)]
   • G: [3, 5]
8. 插入資料 9 到 S（S 滿了，6 被移除）：
   • 6 沒有被訪問過，G 滿了，移除 G 最舊的 3
   • S: [7, 8, 9]
   • M: [4(1)]
   • G: [5, 6]
9. 訪問資料 5：

• G 裡的 5 移至 S，S 滿了，移除 S 最舊的7
  • S: [8, 9, 5]
  • M: [4(1)]
  • G: [6]

這個例子展示了 S3-FIFO 如何通過使用三個隊列來管理資料的插入和淘汰。S 隊列用於臨時儲存新插入的資料，M 隊列用於儲存經常訪問的資料，G 隊列用於記錄被淘汰的資料鍵值。這樣的設計不但確保了高效的快取管理和訪問，還減少了快取未命中的情況。

class CacheItem:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.access_count = 0

class S3FIFO:
    def __init__(self, capacity_s, capacity_m, capacity_g):
        self.capacity_s = capacity_s
        self.capacity_m = capacity_m
        self.capacity_g = capacity_g
        self.cache_s = []
        self.cache_m = []
        self.cache_g = {}

    def get(self, key):
        # 檢查 M 隊列
        for item in self.cache_m:
            if item.key == key:
                item.access_count += 1
                return item.value

        # 檢查 S 隊列
        for item in self.cache_s:
            if item.key == key:
                item.access_count += 1
                return item.value

        # 檢查 G 隊列
        if key in self.cache_g:
            item = self.cache_g.pop(key)
            self.cache_s.append(item)  # 重新插入 S 隊列
            if len(self.cache_s) > self.capacity_s:
                self.evict_s()
            return item.value

        return -1  # 如果 key 不在快取中，返回 -1

    def put(self, key, value):
        # 檢查 key 是否在 M 隊列中
        for item in self.cache_m:
            if item.key == key:
                item.value = value
                return

        # 檢查 key 是否在 S 隊列中並更新
        for item in self.cache_s:
            if item.key == key:
                item.value = value
                return

        # 檢查 key 是否在 G 隊列中
        if key in self.cache_g:
            item = self.cache_g.pop(key)
            item.value = value
            self.cache_s.append(item)  # 重新插入 S 隊列
            if len(self.cache_s) > self.capacity_s:
                self.evict_s()
            return

        # 如果 key 不在任何快取中，則插入到 S 隊列
        new_item = CacheItem(key, value)
        self.cache_s.append(new_item)
        if len(self.cache_s) > self.capacity_s:
            self.evict_s()

    def evict_s(self):
        item = self.cache_s.pop(0)
        if item.access_count > 0:
            self.cache_m.append(item)
            if len(self.cache_m) > self.capacity_m:
                self.evict_m()
        else:
            self.cache_g[item.key] = item
            if len(self.cache_g) > self.capacity_g:
                self.evict_g()

    def evict_m(self):
        while len(self.cache_m) > self.capacity_m:
            item = self.cache_m.pop(0)
            if item.access_count > 0:
                item.access_count -= 1
                self.cache_m.append(item)
            else:
                self.cache_g[item.key] = item
                if len(self.cache_g) > self.capacity_g:
                    self.evict_g()

    def evict_g(self):
        if self.cache_g:
            oldest_key = next(iter(self.cache_g))
            del self.cache_g[oldest_key]

if __name__ == '__main__':
    cache = S3FIFO(capacity_s=3, capacity_m=5, capacity_g=2)
    cache.put(1, 'A')
    cache.put(2, 'B')
    cache.put(3, 'C')
    print(cache.get(1))  # 輸出: 'A'（增加訪問次數）
    cache.put(4, 'D')
    cache.put(5, 'E')
    cache.put(6, 'F')
    print(cache.get(2))  # 輸出: 'B'（資料 2 仍在 M 隊列中）
    print(cache.get(3))  # 輸出: None（資料 3 被移到 G 隊列後再次插入 S 隊列）

    # 更新資料
    cache.put(1, 'AA')
    print(cache.get(1))  # 輸出: 'AA'（更新後的值）

S3-FIFO 相比 LRU，雖然有其優勢，但也存在一些缺點和潛在的限制：

1. 過度淘汰新資料：
   • S3-FIFO 在快速淘汰一次性使用的資料時，可能會過度淘汰一些潛在有價值的新資料，尤其是在資料訪問模式變化較大的情況下。
   • 比如，某些資料可能在短時間內只被訪問一次，但稍後會被頻繁訪問。這些資料可能會被 S3-FIFO 過早淘汰，導致更多的快取未命中。
2. G快取的大小限制：
   • G快取的大小是有限的，一旦達到容量限制，最舊的資料會被移除，這可能會導致一些資料被頻繁重複插入和移除，增加了快取管理的開銷。
   • LRU 不存在這個問題，因為 LRU 的設計不需要額外的鬼快取來管理淘汰的資料。
3. 對工作負載模式的敏感性：
   • S3-FIFO 的性能依賴於工作負載的模式，對於高度局部性和頻繁重訪問的工作負載可能效果很好，但對於那些有較多新資料插入的工作負載可能表現不如 LRU。
   • LRU 在處理不同工作負載模式方面更具通用性，因為它總是保留最近訪問的資料。
4. 實現和調整的複雜性：
   • 雖然 S3-FIFO 在理論上較為簡單，但在實際實現中，需要仔細調整 S、M 和 G 三個隊列的容量，以達到最佳性能。
   • LRU 的實現和調整相對簡單，只需管理一個雙向鏈表或類似的結構。
5. 記憶體消耗：
   • S3-FIFO 雖然能有效利用記憶體資源，但由於需要管理三個隊列，可能會在某些情況下消耗更多的記憶體，特別是在鬼快取 (G) 需要儲存大量資料鍵值時。
   • LRU 只需要管理一個主要隊列，記憶體消耗相對較低。

舉例說明

假設我們有一個快取系統，需要處理一系列訪問模式變化較大的資料：

1. S3-FIFO 的情況：
   • 在初期插入大量新資料時，由於 S 隊列容量有限，很多新資料會被快速淘汰，進入 G 隊列。
   • 如果這些新資料在後續被頻繁訪問，會導致大量快取未命中，因為這些資料已被移出 S 隊列。
2. LRU 的情況：
   • 在初期插入大量新資料時，LRU 會保留最近訪問的資料，並逐步淘汰最久未被訪問的資料。
   • 這樣的設計能夠更好地適應訪問模式變化，確保最近被訪問的資料能夠保留在快取中，減少cache miss。

總結

S3-FIFO 以其簡單、高效和低資源消耗的特點，為快取管理提供了一個優秀的選擇。相比LRU，S3-FIFO更適合在大Cache的環境，但是針對訪問模式變化較大的資料或是系統，還是可以考慮原有的LRU快取策略。

如果喜歡我的文章的話，歡迎追蹤我的部落格: https://kaichiachen.github.io/2024/04/02/s3-fifo/